心之所向便是光

Leetcode 11.盛最多水的容器

  • 2021-05-22
  • 作者 Ender
  • 2.90K 字
  • 次阅读

题目描述：

给你 $n$ 个非负整数 $a_1，a_2，…，a_n$，每个数代表坐标中的一个点 $(i, a_i)$ 。在坐标内画 $n$ 条垂直线，垂直线 $i$ 的两个端点分别为 $(i, a_i)$ 和 $(i, 0)$ 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器。

示例 1：

1
2
3
输入：[1,8,6,2,5,4,8,3,7]
输出：49 
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例 2：

1
2
输入：height = [1,1]
输出：1

示例 3：

1
2
输入：height = [4,3,2,1,4]
输出：16

示例 4：

1
2
输入：height = [1,2,1]
输出：2

提示：

  • $n = height.length$
  • $2 <= n <= 3 * 10^4$
  • $0 <= height[i] <= 3 * 10^4$

链接：

https://leetcode-cn.com/problems/container-with-most-water

题目分析

1.暴力解法

  直接对数组进行双层遍历，两个变量分别表示容器的两边下标。那么水容量就是短边乘上容器宽，记录最大容量即可。不出意外，这样的算法超时了。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int maxArea(vector<int>& height) {
        int maxwater = 0;
        for(int i = 0; i < height.size(); i++){
            for(int j = i+1; j < height.size(); j++){
                int water = min(height[i], height[j])*(j-i);
                if(water > maxwater) maxwater = water;
            }
        }
        return maxwater;
    }
};

  时间复杂度：$O(n^2)$，$n$ 表示数组大小。
  空间复杂度：$O(1)$。我们只需要常数个变量进行记录。

2.暴力解法改进

  考虑到，如果我们遍历的时候，从两边往中间遍历，宽是不断变小的，如果边也在同时变小的话，那么肯定不是最大的容量，对于这样的情况是可以进行剪枝的。于是我们稍微修改了遍历的顺序，容器左壁从左边开始遍历，容器右壁从右边开始遍历。分别记录左右边最大值，小于这个值的情况就可以直接进行剪枝了。内层遍历结束后，我们需要将右壁的最大值归为 0 再进行下一个内层遍历。经过剪枝后刚好能够通过测试，并不优良，因为本质上还是双层遍历。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int maxArea(vector<int>& height) {
        int maxwater = 0, maxleft = 0, maxright = 0;
        for(int i = 0; i < height.size(); i++){
            if(height[i] <= maxleft) continue;
            else maxleft = height[i];

            for(int j = height.size()-1; j > i; j--){
                if(height[j] <= maxright) continue;
                else maxright = height[j];

                maxwater = max(maxwater, min(height[i], height[j])*(j-i));
            }
            maxright = 0;
        }
        return maxwater;
    }
};

  时间复杂度：$O(n^2)$，$n$ 表示数组大小。虽然经过剪枝，但本质上还是双层遍历。
  空间复杂度：$O(1)$。我们只需要常数个变量进行记录。

3.双指针解法

  其实上面的暴力解法改进的思路已经非常接近双指针的思路了。上面的暴力解法都是先确定左壁再遍历右壁进行计算，但实际上，容器高只取决于短的那条边。那么如果我们还是从左右两边往中间遍历，是不是可以按照实际情况选择移动左壁还是右壁呢？实际上我们应该移动短的那边就可以了。因为进行移动的话，容器宽变小了，而容器高却还是取决于短边，移动长边不会增加还可能更少，因此一定不会使容量更大。而移动短边的话，可能提高了容器高的值，就可能使容量增大。所以我们实际上只需要进行一层遍历，两个指针开始时分别在数组两端表示两个容器壁，而后短边不断向对方移动，每次移动的时候判断容积是否变大，变大则更新结果，最后直到两个容器壁相遇则结束。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int maxArea(vector<int>& height) {
        int maxwater = 0, left = 0, right = height.size()-1;
        while(left < right){
            maxwater = max(maxwater, min(height[left], height[right])*(right-left));
            (height[left] < height[right])?(left++):(right--);
        }
        return maxwater;
    }
};

  时间复杂度：$O(n)$，$n$ 表示数组大小。两个指针从左右两端开始遍历直到相遇，总共只对数组进行了一层遍历。
  空间复杂度：$O(1)$。我们只需要常数个变量进行记录。

本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可
,
最后编辑：2021-06-26